Generalized colorings and avoidable orientations

Jenő Szigeti; Zsolt Tuza

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 137-145
  • ISSN: 2083-5892

Abstract

top
Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.

How to cite

top

Jenő Szigeti, and Zsolt Tuza. "Generalized colorings and avoidable orientations." Discussiones Mathematicae Graph Theory 17.1 (1997): 137-145. <http://eudml.org/doc/270174>.

@article{JenőSzigeti1997,
abstract = {Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.},
author = {Jenő Szigeti, Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary property; graph coloring; generalized colorings; hereditary properties; avoidable orientations},
language = {eng},
number = {1},
pages = {137-145},
title = {Generalized colorings and avoidable orientations},
url = {http://eudml.org/doc/270174},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Jenő Szigeti
AU - Zsolt Tuza
TI - Generalized colorings and avoidable orientations
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 137
EP - 145
AB - Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.
LA - eng
KW - hereditary property; graph coloring; generalized colorings; hereditary properties; avoidable orientations
UR - http://eudml.org/doc/270174
ER -

References

top
  1. [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  2. [2] J. Bucko, M. Frick, P. Mihók and R. Vasky, Uniquely partitionable graphs, Discussiones Mathematicae Graph Theory 17 (1997) 103-113, doi: 10.7151/dmgt.1043. Zbl0906.05057
  3. [3] Y. Caro, Private communication, 1989. 
  4. [4] T. Gallai, On directed paths and circuits, in: P. Erd os and G.O.H. Katona, eds., Theory of Graphs, Proc. Colloq. Math. Soc. János Bolyai, Tihany (Hungary) 1966 (Academic Press, San Diego, 1968) 115-118. 
  5. [5] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
  6. [6] G.J. Minty, A theorem on n-colouring the points of a linear graph, Amer. Math. Monthly 67 (1962) 623-624, doi: 10.2307/2310826. Zbl0108.36601
  7. [7] R. Roy, Nombre chromatique et plus longs chemins d'un graphe, Revue AFIRO 1 (1967) 127-132. Zbl0157.31302
  8. [8] Zs. Tuza, Graph coloring in linear time, J. Combin. Theory (B) 55 (1992) 236-243, doi: 10.1016/0095-8956(92)90042-V. Zbl0709.05019
  9. [9] Zs. Tuza, Chromatic numbers and orientations, Unpublished manuscript, February 1993. 
  10. [10] Zs. Tuza, Some remarks on the Gallai-Roy Theorem, in preparation. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.