Complexity of colouring problems restricted to uni chord-free and free graphs

3,000 تومان


Inthispaper, wedealwithsimpleconnectedgraphs.AgraphGhasvertexsetV(G)andedgesetE(G)</p>

<.Anelement ofGis one of its vertices or edges, and the set of elements of G is denoted by S(G) := V(G)∪E(G). Two vertices u,v ∈ V(G) are adjacent ifuv ∈E(G);twoedgese1,e2 ∈E(G) areadjacent iftheyshareacommonendvertex;avertexuandanedgeeare incident if u is an endvertex of e. For a graph G = (V,E) and V′ ⊆ V, G[V′]denotes the subgraph of G induced by V′.

The degreeofavertexv inGisthenumberofedgesofGincidenttov.WeusethestandardnotationKn,Km,n,and Cn forcomplete graphs,completebipartitegraphs,andcyclegraphs,respectively.

Anedge colouringisanassociationofcolourstotheedgesofagraphinsuchawaythatnoadjacentedgesreceivethesame colour.

ThechromaticindexofagraphG,denoted χ′(G),istheleastnumberofcolourssufficienttoedge-colourthisgraph. Clearly, χ′(G) ≥ ∆(G),where ∆(G) denotes the maximum degree of avertexinG. Vizing’s theorem[14] states thatevery graph G can be edge-coloured with ∆(G)+1 colours. By Vizing’s theorem, only two values are possible for the chromatic index of a graph: χ′(G) = ∆(G) or ∆(G)+1.

If a graph G has chromatic index ∆(G), then G is said to be Class 1; if G has chromaticindex ∆(G)+1,thenGissaidtobeClass2. Atotal-colouringisanassociationofcolourstotheelementsofagraphinsuchawaythatnoadjacentorincidentelements receive the same colour.

The total chromatic number of a graph G, denoted χT(G), is the least number of colours sufficient to total-colour this graph. Clearly, χT(G) ≥ ∆(G)+1. The total-colouring conjecture (TCC) states that every graph G can betotal-colouredwith ∆(G)+2colours.