On Total and Edge-colouring of Proper Circular-arc Graphs
Resumo
Deciding if a graph is Δ-edge-colourable (resp. (Δ + 1)-total colourable), although it is an NP-complete problem for graphs in general, is polynomially solvable for interval graphs of odd (resp. even) maximum degree Δ. An interesting superclass of the proper interval graphs are the proper circular-arc graphs, for which we suspect that Δ-edge-colourability is linear-time decidable. This work presents sufficient conditions for Δ-edge-colourability, (Δ + 1)-total colourability, and (Δ+2)-total colourability of proper circular-arc graphs. Our proofs are constructive and yield polynomial-time algorithms.
Referências
Behzad, M. (1965). Graphs and their chromatic numbers. PhD thesis, Michigan State University.
Behzad, M., Chartrand, G., and Cooper Jr., J. K. (1967). The color numbers of complete graphs. J. London Math. Soc., 42:226–228.
Booth, K. S. and Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci., 13:335–379.
Campos, C. N., Figueiredo, C. M. H., Machado, R., and Mello, C. P. (2012). The total chromatic number of split-indifference graphs. Discrete Math., 312:2690–2693.
Figueiredo, C. M. H., Meidanis, J., and Mello, C. P. (1997). On edge-colouring indifference graphs. Theor. Comput. Sci., 181:91–106.
Figueiredo, C. M. H., Meidanis, J., Mello, C. P., and Ortiz, C. (2003). Decompositions for the edge colouring of reduced indifference graphs. Theor. Comput. Sci., 297:145–155.
Garey, M. R., Johnson, D. S., Miller, G. L., and Papadimitriou, C. H. (1980). The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods, 1(2):216–227.
Grötschel, M., Lovász, L., and Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197.
Hilton, A. J. W. and Johnson, P. D. (1987). Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Cambridge Philos. Soc., 102:103–112.
Holyer, I. (1981). The NP-completeness of edge-colouring. SIAM J. Comput., 10(4):718–720.
McConnell, R. M. (2003). Linear-time recognition of circular-arc graphs. 37:93–147.
Roberts, F. S. (1969). Indifference graphs. In Proc. 2nd Ann Arbor Graph Theory Conference, pages 139–146, Ann Arbor, USA.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., 78:315–319.
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz., 3:25–30.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russian Math. Surveys, 23:125–141.
Behzad, M., Chartrand, G., and Cooper Jr., J. K. (1967). The color numbers of complete graphs. J. London Math. Soc., 42:226–228.
Booth, K. S. and Lueker, G. S. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci., 13:335–379.
Campos, C. N., Figueiredo, C. M. H., Machado, R., and Mello, C. P. (2012). The total chromatic number of split-indifference graphs. Discrete Math., 312:2690–2693.
Figueiredo, C. M. H., Meidanis, J., and Mello, C. P. (1997). On edge-colouring indifference graphs. Theor. Comput. Sci., 181:91–106.
Figueiredo, C. M. H., Meidanis, J., Mello, C. P., and Ortiz, C. (2003). Decompositions for the edge colouring of reduced indifference graphs. Theor. Comput. Sci., 297:145–155.
Garey, M. R., Johnson, D. S., Miller, G. L., and Papadimitriou, C. H. (1980). The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discrete Methods, 1(2):216–227.
Grötschel, M., Lovász, L., and Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197.
Hilton, A. J. W. and Johnson, P. D. (1987). Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Cambridge Philos. Soc., 102:103–112.
Holyer, I. (1981). The NP-completeness of edge-colouring. SIAM J. Comput., 10(4):718–720.
McConnell, R. M. (2003). Linear-time recognition of circular-arc graphs. 37:93–147.
Roberts, F. S. (1969). Indifference graphs. In Proc. 2nd Ann Arbor Graph Theory Conference, pages 139–146, Ann Arbor, USA.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., 78:315–319.
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz., 3:25–30.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russian Math. Surveys, 23:125–141.
Publicado
26/07/2018
Como Citar
BERNARDI, João Pedro W.; DE ALMEIDA, Sheila M.; ZATESKO, Leandro M..
On Total and Edge-colouring of Proper Circular-arc Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 157-160.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3557.
