Caracterização e coloração total de grafos bipartidos com até três bicliques

Abstract

The total chromatic number of a graph 𝐺 is the least number of colours necessary to colour all the vertices and edges of 𝐺 só that no adjacent elements have the same colour. Determining the total chromatic number of a graph is an important hard problem that has been studied for many graph classes, including graphs with few cliques. For graphs with a universal vertex, it was solved by Hilton in 1990. If the total chromatic number of a graph 𝐺 is ∆(𝐺) + 1, 𝐺 is said to be Type 1. If it is ∆(𝐺) + 2, then 𝐺 is Type 2. In 2012, Campos et al. solved the problem for split-indifference graphs, all of which have at most three cliques, proving that such a graph 𝐺 is: Type 2 if 𝐺 has some ∆-subgraph 𝐻 (i.e a subgraph with ∆(𝐻) = ∆(𝐺)) which has a universal vertex and is Type 2; Type 1 otherwise. In 1991, Hilton also solved the problem for bipartite graphs with adjacent bi-universal vertices (a vertex in a part of a bipartite graph is bi-universal if it is adjacent to all vertices in the other part). We conjecture that a bipartite graph 𝐺 with at most three bicliques is: Type 2 if 𝐺 has some Type 2 ∆-subgraph with adjacent bi-universal vertices; Type 1 otherwise. If 𝐺 has at most two bicliques, then the conjecture holds by Hilton’s result. If 𝐺 has three bicliques, we prove that the graph obtained after successively removing twins is either a 𝑃5 or has adjacent bi-universal vertices. For the former case, let 𝐴, 𝐵, 𝐶, 𝐷, 𝐸 be the sets of twin vertices, where the 𝑃5 is given by the sequence 𝐴𝐵𝐶𝐷𝐸, being 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 their corresponding cardinalities, with 𝑎 ≥ 𝑒 without loss of generality. Then, we prove that our conjecture holds for all the following cases: 𝑏 + 𝑑 ̸= 𝑐 + 𝑎; 𝑏 + 𝑑 = 𝑐 + 𝑎 > 𝑎𝑑 + min(𝑎, 𝑑); max(𝑑, 𝑒) < 𝑎 and 𝑎𝑑 ≥ 𝑏. So, the conjecture remains open when 𝑏 + 𝑑 = 𝑐 + 𝑎 ≤ 𝑎𝑑 + min(𝑎, 𝑑) and: either 𝑑 ≥ 𝑎, or 𝑎 = 𝑒 > 𝑑.