{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29956"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29956","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Extremal problems in graph theory","abstract":"We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\\ge{3\\over4}k\\sp2\\pm k,$ depending on whether k is even or odd. The path chromatic number $\\chi\\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of paths. We characterize cartesian products of cycles with path chromatic number 2. We show that if G is a toroidal graph, then for any non-contractible chordless cycle C of G, there is a 3-coloring of the vertices of G so that each color class except one induces a disjoint union of paths, while the third color class induces a disjoint union of paths and the cycle C. The path list chromatic number of a graph, $\\\\chi\\sb{P}(G),$ is the minimum k for which, given any assignment of lists of size k to each vertex, G can be colored by assigning each vertex a color from its list so that each color class induces a disjoint union of paths. We prove that $\\\\chi\\sb{P}(G)\\le3.$ The observability of a graph G is least number of colors in a proper edge-coloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a set-balanced k-edge-coloring if the edges of G can be properly colored with k colors so that, for each degree, the color sets at vertices of that degree occur with multiplicities differing by at most one. We determine the values of k such that G has a set-balanced k-edge-coloring whenever G is a member of various classes of graphs. The spot-chromatic number of a graph, $\\chi\\sb{S}(G),$ is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of cliques. We show that $\\chi\\sb{S}(K\\sb{mt}\\ \\square\\ K\\sb{nt})\\le{mnt\\over m+n}+2\\min(m,n)$ whenever $m+n$ divides t. Let ${\\cal G}\\sb0=\\{K\\sb1\\}.$ For $k\\ge1,$ the family ${\\cal G}\\sb{k}$ of twisted hypercubes of dimension k is the set of graphs constructible by adding a matching joining two graphs in ${\\cal G}\\sb{k-1}.$ We construct a family of twisted hypercubes of small diameter. We prove that the order of growth of the minimum diameter among twisted hypercubes of dimension k is $\\Theta(k$/lg k). The domination number $\\gamma(G)$ of a graph G is the minimum size of a set S such that every vertex of G is in S or is adjacent to some vertex in S. The Kneser graph $K(n, k)$ has as vertices the k-subsets of $\\lbrack n\\rbrack.$ We determine $\\gamma(K(n,k))$ when $n\\ge{3\\over4}k\\sp2\\pm k$ depending on the parity of k.","abstract_html":"We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\\ge{3\\over4}k\\sp2\\pm k,$ depending on whether k is even or odd. The path chromatic number $\\chi\\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of paths. We characterize cartesian products of cycles with path chromatic number 2. We show that if G is a toroidal graph, then for any non-contractible chordless cycle C of G, there is a 3-coloring of the vertices of G so that each color class except one induces a disjoint union of paths, while the third color class induces a disjoint union of paths and the cycle C. The path list chromatic number of a graph, $\\\\chi\\sb{P}(G),$ is the minimum k for which, given any assignment of lists of size k to each vertex, G can be colored by assigning each vertex a color from its list so that each color class induces a disjoint union of paths. We prove that $\\\\chi\\sb{P}(G)\\le3.$ The observability of a graph G is least number of colors in a proper edge-coloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a set-balanced k-edge-coloring if the edges of G can be properly colored with k colors so that, for each degree, the color sets at vertices of that degree occur with multiplicities differing by at most one. We determine the values of k such that G has a set-balanced k-edge-coloring whenever G is a member of various classes of graphs. The spot-chromatic number of a graph, $\\chi\\sb{S}(G),$ is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of cliques. We show that <span class=\"etd-inline-math\">\\chi\\sb{S}(K\\sb{mt} \\square K\\sb{nt})\\le{mnt\\over m+n}+2\\min(m,n)</span> whenever $m+n$ divides t. Let ${\\cal G}\\sb0=\\{K\\sb1\\}.$ For $k\\ge1,$ the family ${\\cal G}\\sb{k}$ of twisted hypercubes of dimension k is the set of graphs constructible by adding a matching joining two graphs in ${\\cal G}\\sb{k-1}.$ We construct a family of twisted hypercubes of small diameter. We prove that the order of growth of the minimum diameter among twisted hypercubes of dimension k is $\\Theta(k$/lg k). The domination number <span class=\"etd-inline-math\">&gamma;(G)</span> of a graph G is the minimum size of a set S such that every vertex of G is in S or is adjacent to some vertex in S. The Kneser graph $K(n, k)$ has as vertices the k-subsets of $\\lbrack n\\rbrack.$ We determine <span class=\"etd-inline-math\">&gamma;(K(n,k))</span> when $n\\ge{3\\over4}k\\sp2\\pm k$ depending on the parity of k.","abstract_has_math":true,"creators":["Hartman, Christopher M."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Weichsel, Paul M.","Francis, George K.","Edelsbrunner, Herbert"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-03-01T19:31:13Z","date_published":"2012-03-01T19:31:13Z","updated_at":"2026-07-22T22:25:29Z","subjects":["graph theory"],"languages":["en"],"rights":["Copyright 1997 Christopher M. Hartman"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29956","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Weichsel, Paul M.","Francis, George K.","Edelsbrunner, Herbert"]},{"key":"dc:creator","label":"Author","values":["Hartman, Christopher M."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-03-01T19:31:13Z","1997"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["graph theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1997 Christopher M. Hartman"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29956"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\\ge{3\\over4}k\\sp2\\pm k,$ depending on whether k is even or odd. The path chromatic number $\\chi\\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of paths. We characterize cartesian products of cycles with path chromatic number 2. We show that if G is a toroidal graph, then for any non-contractible chordless cycle C of G, there is a 3-coloring of the vertices of G so that each color class except one induces a disjoint union of paths, while the third color class induces a disjoint union of paths and the cycle C. The path list chromatic number of a graph, $\\\\chi\\sb{P}(G),$ is the minimum k for which, given any assignment of lists of size k to each vertex, G can be colored by assigning each vertex a color from its list so that each color class induces a disjoint union of paths. We prove that $\\\\chi\\sb{P}(G)\\le3.$ The observability of a graph G is least number of colors in a proper edge-coloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a set-balanced k-edge-coloring if the edges of G can be properly colored with k colors so that, for each degree, the color sets at vertices of that degree occur with multiplicities differing by at most one. We determine the values of k such that G has a set-balanced k-edge-coloring whenever G is a member of various classes of graphs. The spot-chromatic number of a graph, $\\chi\\sb{S}(G),$ is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of cliques. We show that $\\chi\\sb{S}(K\\sb{mt}\\ \\square\\ K\\sb{nt})\\le{mnt\\over m+n}+2\\min(m,n)$ whenever $m+n$ divides t. Let ${\\cal G}\\sb0=\\{K\\sb1\\}.$ For $k\\ge1,$ the family ${\\cal G}\\sb{k}$ of twisted hypercubes of dimension k is the set of graphs constructible by adding a matching joining two graphs in ${\\cal G}\\sb{k-1}.$ We construct a family of twisted hypercubes of small diameter. We prove that the order of growth of the minimum diameter among twisted hypercubes of dimension k is $\\Theta(k$/lg k). The domination number $\\gamma(G)$ of a graph G is the minimum size of a set S such that every vertex of G is in S or is adjacent to some vertex in S. The Kneser graph $K(n, k)$ has as vertices the k-subsets of $\\lbrack n\\rbrack.$ We determine $\\gamma(K(n,k))$ when $n\\ge{3\\over4}k\\sp2\\pm k$ depending on the parity of k.","Submitted by Sarah Shreeves (sshreeve@illinois.edu) on 2012-03-01T19:31:13Z No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) On behalf of Chris Hartman - email sent to IDEALS-gen on January 11, 2012","Made available in DSpace on 2012-03-01T19:31:13Z (GMT). No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) Previous issue date: 1997"]},{"key":"dc:title","label":"Title","values":["Extremal problems in graph theory"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Weichsel, Paul M.","Francis, George K.","Edelsbrunner, Herbert"],"dc:creator":["Hartman, Christopher M."],"dc:date":["2012-03-01T19:31:13Z","1997"],"dc:description":["We consider generalized graph coloring and other extremal problems in graph theory. We also construct twisted hypercubes of small radius and find the domination number of the Kneser graph $K(n,k)$ when $n\\ge{3\\over4}k\\sp2\\pm k,$ depending on whether k is even or odd. The path chromatic number $\\chi\\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of paths. We characterize cartesian products of cycles with path chromatic number 2. We show that if G is a toroidal graph, then for any non-contractible chordless cycle C of G, there is a 3-coloring of the vertices of G so that each color class except one induces a disjoint union of paths, while the third color class induces a disjoint union of paths and the cycle C. The path list chromatic number of a graph, $\\\\chi\\sb{P}(G),$ is the minimum k for which, given any assignment of lists of size k to each vertex, G can be colored by assigning each vertex a color from its list so that each color class induces a disjoint union of paths. We prove that $\\\\chi\\sb{P}(G)\\le3.$ The observability of a graph G is least number of colors in a proper edge-coloring of G such that the color sets at vertices of G are pairwise distinct. A graph G has a set-balanced k-edge-coloring if the edges of G can be properly colored with k colors so that, for each degree, the color sets at vertices of that degree occur with multiplicities differing by at most one. We determine the values of k such that G has a set-balanced k-edge-coloring whenever G is a member of various classes of graphs. The spot-chromatic number of a graph, $\\chi\\sb{S}(G),$ is the least number of colors with which the vertices of G can be colored so that each color class induces a disjoint union of cliques. We show that $\\chi\\sb{S}(K\\sb{mt}\\ \\square\\ K\\sb{nt})\\le{mnt\\over m+n}+2\\min(m,n)$ whenever $m+n$ divides t. Let ${\\cal G}\\sb0=\\{K\\sb1\\}.$ For $k\\ge1,$ the family ${\\cal G}\\sb{k}$ of twisted hypercubes of dimension k is the set of graphs constructible by adding a matching joining two graphs in ${\\cal G}\\sb{k-1}.$ We construct a family of twisted hypercubes of small diameter. We prove that the order of growth of the minimum diameter among twisted hypercubes of dimension k is $\\Theta(k$/lg k). The domination number $\\gamma(G)$ of a graph G is the minimum size of a set S such that every vertex of G is in S or is adjacent to some vertex in S. The Kneser graph $K(n, k)$ has as vertices the k-subsets of $\\lbrack n\\rbrack.$ We determine $\\gamma(K(n,k))$ when $n\\ge{3\\over4}k\\sp2\\pm k$ depending on the parity of k.","Submitted by Sarah Shreeves (sshreeve@illinois.edu) on 2012-03-01T19:31:13Z No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) On behalf of Chris Hartman - email sent to IDEALS-gen on January 11, 2012","Made available in DSpace on 2012-03-01T19:31:13Z (GMT). No. of bitstreams: 1 Hartman_Christopher.pdf: 2653633 bytes, checksum: 1588fa0ba80b477739db059a0e5fc587 (MD5) Previous issue date: 1997"],"dc:identifier":["http://hdl.handle.net/2142/29956"],"dc:language":["en"],"dc:rights":["Copyright 1997 Christopher M. Hartman"],"dc:subject":["graph theory"],"dc:title":["Extremal problems in graph theory"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}