0000000000062202

AUTHOR

Grzegorz Kubicki

showing 3 related works from this author

An efficient algorithm for stopping on a sink in a directed graph

2013

Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.

Factor-critical graphDiscrete mathematicsApplied MathematicsNeighbourhood (graph theory)Directed graphManagement Science and Operations ResearchBiconnected graphIndustrial and Manufacturing EngineeringHypercube graphCombinatoricsWheel graphPath graphGraph factorizationSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsOperations Research Letters
researchProduct

Chromatic sums for colorings avoiding monochromatic subgraphs

2015

Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …

Vertex (graph theory)Computational complexity theoryApplied MathematicsChromatic sumValue (computer science)forbidden subgraphsCombinatoricsGreedy coloringIntegerQA1-939sum of colorsDiscrete Mathematics and CombinatoricsChromatic scaleMonochromatic colorcoloringMathematicsMathematicsDiscussiones Mathematicae Graph Theory
researchProduct

Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

2013

Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …

Discrete mathematicsCombinatoricsGreedy coloringVertex (graph theory)Edge coloringApplied MathematicsDiscrete Mathematics and CombinatoricsMonochromatic colorChromatic scaleComplete coloringFractional coloringBrooks' theoremMathematicsElectronic Notes in Discrete Mathematics
researchProduct