Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs

Hortensia Galeana-Sánchez; R. Rojas-Monroy; B. Zavala

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 337-347
  • ISSN: 2083-5892

Abstract

top
We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.

How to cite

top

Hortensia Galeana-Sánchez, R. Rojas-Monroy, and B. Zavala. "Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 337-347. <http://eudml.org/doc/270653>.

@article{HortensiaGaleana2009,
abstract = {We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.},
author = {Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {m-coloured digraph; 3-quasitransitive digraph; kernel by monochromatic paths; γ-cycle; quasi-monochromatic digraph; -coloured digraph; -cycle},
language = {eng},
number = {2},
pages = {337-347},
title = {Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs},
url = {http://eudml.org/doc/270653},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - R. Rojas-Monroy
AU - B. Zavala
TI - Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 337
EP - 347
AB - We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.
LA - eng
KW - m-coloured digraph; 3-quasitransitive digraph; kernel by monochromatic paths; γ-cycle; quasi-monochromatic digraph; -coloured digraph; -cycle
UR - http://eudml.org/doc/270653
ER -

References

top
  1. [1] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161, doi: 10.1002/jgt.3190200205. Zbl0832.05048
  2. [2] J. Bang-Jensen and J. Huang, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27, doi: 10.1016/S0012-365X(97)00179-9. Zbl0955.05048
  3. [3] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985). 
  4. [4] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. 
  5. [5] P. Duchet, Classical Perfect Graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67-96. Zbl0558.05038
  6. [6] P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8. Zbl0456.05032
  7. [7] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V. Zbl0857.05054
  8. [8] H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3. Zbl0958.05061
  9. [9] H. Galena-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6. Zbl0529.05024
  10. [10] H. Galeana-Sánchez and V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257-265, doi: 10.1016/0012-365X(86)90172-X. Zbl0593.05034
  11. [11] H. Galeana-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs, submitted. Zbl1217.05089
  12. [12] Ghouilá-Houri, Caractérisation des graphes non orientés dont on peut orienter les aretes de maniére à obtenir le graphe d'une relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371. Zbl0105.35503
  13. [13] S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7. Zbl0654.05033
  14. [14] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755. Zbl0053.02902
  15. [15] M. Richardson, Extensions theorems for solutions of irreflexive relations, Proc. Nat. Acad. Sci. USA 39 (1953) 649, doi: 10.1073/pnas.39.7.649. Zbl0053.02903
  16. [16] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8. Zbl0488.05036

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.