Nombre chromatique et plus longs chemins d'un graphe

DOI10.1051/m2an/1967010501291zbMath0157.31302OpenAlexW60957894MaRDI QIDQ5539654

Bernard Roy

Publication date: 1967

Published in: Revue française d'informatique et de recherche opérationnelle (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/193088

zbMATH Keywords

topology

Related Items (96)

Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths ⋮ On k-optimum dipath partitions and partial k-colourings of acyclic digraphs ⋮ Acyclic subgraphs with high chromatic number ⋮ Weighted Rooted Trees: Fat or Tall? ⋮ Acyclic Orientations with Path Constraints ⋮ Monochromatic directed walks in arc-colored directed graphs ⋮ Paths with two blocks in \(k\)-chromatic digraphs ⋮ Antidirected paths in 5-chromatic digraphs ⋮ Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\) ⋮ A note on strong perfectness of graphs ⋮ Trees contained in every orientation of a graph ⋮ Local \(k\)-colorings of graphs and hypergraphs ⋮ \( \chi \)-diperfect digraphs ⋮ Bispindles in strongly connected digraphs with large chromatic number ⋮ Oriented expressions of graph properties ⋮ Graph saturation games ⋮ Ramsey-nice families of graphs ⋮ Motivations and history of some of my conjectures ⋮ On edge orienting methods for graph coloring ⋮ Efficient enumeration of graph orientations with sources ⋮ On greene's theorem for digraphs ⋮ Mixed graph colorings ⋮ A Ramsey type result for oriented trees ⋮ Variations on the Gallai-Milgram theorem ⋮ On the Turán number of some ordered even cycles ⋮ Independent sets which meet all longest paths ⋮ Simple proofs of results on paths representing all colors in proper vertex-colorings ⋮ On properly ordered coloring of vertices in a vertex-weighted graph ⋮ Optimal colorings with rainbow paths ⋮ A note on orientation and chromatic number of graphs ⋮ Problems on cycles and colorings ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ Bispindle in strongly connected digraphs with large chromatic number ⋮ Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs ⋮ Paths with two blocks in \(n\)-chromatic digraphs ⋮ On colorings and orientations of signed graphs ⋮ Monochromatic paths in random tournaments ⋮ On \(\chi \)-diperfect digraphs with stability number two ⋮ The existence of a path with two blocks in digraphs ⋮ The size Ramsey number of a directed path ⋮ Unnamed Item ⋮ Congruence of cycle lengths and chromatic number ⋮ Existence of paths with \(t\) blocks in \(k ( t )\)-chromatic digraph ⋮ Many Facets of Dualities ⋮ Interleaved adjoints of directed graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Uncolorable mixed hypergraphs ⋮ k-optimal partitions of a directed graph ⋮ Orientations of graphs with prescribed weighted out-degrees ⋮ Coloring digraphs with forbidden cycles ⋮ A dualistic approach to bounding the chromatic number of a graph ⋮ Subdivisions of four blocks cycles in digraphs with large chromatic number ⋮ On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem ⋮ On the strong and the semi-strong path partition conjecture ⋮ On Linial's conjecture for spine digraphs ⋮ Claws in digraphs ⋮ Gallai's problem on Dirac's construction ⋮ Variable space search for graph coloring ⋮ On the strong path partition conjecture of Berge ⋮ WORM colorings of planar graphs ⋮ On Greene-Kleitman's theorem for general digraphs ⋮ Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs ⋮ Graph labellings with variable weights, a survey ⋮ Stable set meeting every longest path ⋮ On the Berge's strong path partition conjecture ⋮ Induced subgraphs of graphs with large chromatic number. XIII. New brooms ⋮ Ramsey numbers for tournaments ⋮ Acyclic orientations of a graph and the chromatic and independence numbers ⋮ Path homomorphisms, graph colorings, and boolean matrices ⋮ Unnamed Item ⋮ Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs ⋮ Directed Ramsey number for trees ⋮ Structure and colour in triangle-free graphs ⋮ Increasing paths in countable graphs ⋮ The trouble with the second quantifier ⋮ Duality pairs and homomorphisms to oriented and unoriented cycles ⋮ Using stable sets to bound the chromatic number ⋮ Paths, cycles and circular colorings in digraphs ⋮ On some properties of suboptimal colorings of graphs ⋮ Antidirected Hamiltonian paths in tournaments ⋮ Chromatic number and orientations of graphs and signed graphs ⋮ Path Partitions, Cycle Covers and Integer Decomposition ⋮ Monochromatic trees in random tournaments ⋮ On three blocks paths \(P (k, l, r)\) ⋮ Diperfect graphs ⋮ Acyclic subgraphs of tournaments with high chromatic number ⋮ Tournaments and Semicomplete Digraphs ⋮ Lexicographic Orientation Algorithms ⋮ Some Ramsey nu mbers for directed graphs ⋮ Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number ⋮ Submodular functions and rooted trees ⋮ Density via duality. ⋮ Obstructions for acyclic local tournament orientation completions ⋮ Covering and coloring problems for relatives of intervals ⋮ Cycles and new bounds for the chromatic number ⋮ Separating pairs of points of standard boxes

This page was built for publication: Nombre chromatique et plus longs chemins d'un graphe